"""
============================================================================
数组 (Array) - Python实现
============================================================================

【核心定义】
Python的list本质上是动态数组，自动管理内存扩容。
支持O(1)随机访问，但Python的list比C数组更灵活。

【内存布局】
Python list内部结构:
    PyListObject {
        ob_refcnt: 引用计数
        ob_type: 类型对象
        ob_size: 元素数量
        allocated: 已分配空间
        ob_item: 指向元素数组的指针 → [obj1*, obj2*, obj3*, ...]
    }

注意: Python list存储的是对象引用，不是值本身

【时间复杂度】
- 访问: O(1)
- 搜索: O(n)
- 末尾插入: O(1) 均摊
- 任意位置插入: O(n)
- 删除: O(n)

【空间复杂度】O(n)

【Python特色】
- 动态类型，可存储不同类型元素
- 自动内存管理
- 丰富的内置方法
- 负索引支持
"""

from typing import List, Any
import sys


class DynamicArray:
    """自定义动态数组类（模拟list的行为）"""
    
    def __init__(self, capacity: int = 10):
        """初始化数组"""
        self._capacity = capacity
        self._size = 0
        self._data = [None] * capacity
    
    def __len__(self) -> int:
        """返回数组大小"""
        return self._size
    
    def __getitem__(self, index: int) -> Any:
        """支持索引访问 arr[i]"""
        if not -self._size <= index < self._size:
            raise IndexError("索引越界")
        if index < 0:
            index += self._size
        return self._data[index]
    
    def __setitem__(self, index: int, value: Any):
        """支持索引赋值 arr[i] = value"""
        if not -self._size <= index < self._size:
            raise IndexError("索引越界")
        if index < 0:
            index += self._size
        self._data[index] = value
    
    def append(self, value: Any):
        """在末尾添加元素"""
        if self._size >= self._capacity:
            self._resize(2 * self._capacity)  # 扩容为2倍
        self._data[self._size] = value
        self._size += 1
    
    def insert(self, index: int, value: Any):
        """在指定位置插入元素"""
        if not 0 <= index <= self._size:
            raise IndexError("索引越界")
        
        if self._size >= self._capacity:
            self._resize(2 * self._capacity)
        
        # 后移元素
        for i in range(self._size, index, -1):
            self._data[i] = self._data[i-1]
        
        self._data[index] = value
        self._size += 1
    
    def remove(self, index: int) -> Any:
        """删除指定位置的元素"""
        if not 0 <= index < self._size:
            raise IndexError("索引越界")
        
        value = self._data[index]
        
        # 前移元素
        for i in range(index, self._size - 1):
            self._data[i] = self._data[i+1]
        
        self._data[self._size - 1] = None
        self._size -= 1
        
        return value
    
    def _resize(self, new_capacity: int):
        """调整容量"""
        new_data = [None] * new_capacity
        for i in range(self._size):
            new_data[i] = self._data[i]
        self._data = new_data
        self._capacity = new_capacity

    def __repr__(self) -> str:
        """字符串表示"""
        return f"[{', '.join(str(self._data[i]) for i in range(self._size))}]"


# ============================================================================
# 应用场景1: 查找表 - 快速访问
# ============================================================================
def example_lookup_table():
    print("\n=== 应用场景1: 查找表 ===")
    print("场景: 存储每月天数，通过月份索引快速查询\n")
    
    days_in_month = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
    
    month = 7  # 8月
    print(f"第{month + 1}个月有{days_in_month[month]}天")
    print("优势: O(1)时间复杂度，直接索引访问")


# ============================================================================
# 应用场景2: NumPy数组 - 科学计算
# ============================================================================
def example_numpy_array():
    print("\n=== 应用场景2: NumPy数组（科学计算）===")
    print("场景: 图像处理、矩阵运算\n")
    
    # 使用普通list模拟（实际应用会用numpy）
    # 3x3 矩阵表示图像区域
    image = [
        [255, 200, 150],
        [180, 220, 160],
        [140, 190, 210]
    ]
    
    print("原始图像数据:")
    for row in image:
        print(f"  {row}")
    
    # 降低亮度
    processed = [[int(pixel * 0.8) for pixel in row] for row in image]
    
    print("\n降低亮度后:")
    for row in processed:
        print(f"  {row}")
    
    print("\n优势: 连续内存，向量化操作，适合批量处理")


# ============================================================================
# 应用场景3: 缓存实现
# ============================================================================
class SimpleCache:
    """简单的数组缓存"""
    
    def __init__(self, capacity: int = 100):
        self.cache = {}  # 使用字典实现，但原理类似数组
        self.capacity = capacity
        self.access_count = 0
    
    def get(self, key: str) -> Any:
        """获取缓存"""
        self.access_count += 1
        return self.cache.get(key)
    
    def put(self, key: str, value: Any):
        """设置缓存"""
        if len(self.cache) >= self.capacity:
            # 简单策略：删除第一个
            first_key = next(iter(self.cache))
            del self.cache[first_key]
        self.cache[key] = value


def example_cache():
    print("\n=== 应用场景3: 简单缓存 ===")
    print("场景: 缓存最近访问的数据\n")
    
    cache = SimpleCache(capacity=5)
    
    # 添加缓存
    cache.put("user:101", {"name": "张三", "age": 25})
    cache.put("user:102", {"name": "李四", "age": 30})
    
    # 查询缓存
    user = cache.get("user:101")
    print(f"缓存命中: {user}")
    print(f"访问次数: {cache.access_count}")
    print("优势: 连续内存，缓存友好，查找快速")


# ============================================================================
# 应用场景4: Python list的高级特性
# ============================================================================
def example_python_list_features():
    print("\n=== 应用场景4: Python list高级特性 ===")
    print("场景: 展示Python list独有的便利功能\n")
    
    # 列表推导式
    squares = [x**2 for x in range(10)]
    print(f"平方数列表: {squares}")
    
    # 切片操作
    data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    print(f"原始列表: {data}")
    print(f"切片 [2:7]: {data[2:7]}")
    print(f"步长切片 [::2]: {data[::2]}")
    print(f"反转 [::-1]: {data[::-1]}")
    
    # 负索引
    print(f"最后一个元素 [-1]: {data[-1]}")
    print(f"倒数第三个 [-3]: {data[-3]}")
    
    print("\n优势: Python语法糖，代码简洁优雅")



# ============================================================================
# 主函数 - 演示所有功能
# ============================================================================
def main():
    print("╔════════════════════════════════════════╗")
    print("║   数组 (Array) - Python实现            ║")
    print("╚════════════════════════════════════════╝")
    
    # 基本操作演示
    print("\n--- 动态数组基本操作 ---")
    arr = DynamicArray(5)
    
    print("1. 添加元素: ", end="")
    arr.append(10)
    arr.append(20)
    arr.append(30)
    arr.append(40)
    print(arr)
    
    print("2. 在索引1插入元素25: ", end="")
    arr.insert(1, 25)
    print(arr)
    
    print("3. 删除索引2的元素: ", end="")
    arr.remove(2)
    print(arr)
    
    print("4. 获取索引2的元素:", arr[2])
    print("5. 支持负索引 [-1]:", arr[-1])
    
    print(f"\n当前数组状态:")
    print(f"  大小: {len(arr)}")
    print(f"  容量: {arr._capacity}")
    
    # Python原生list演示
    print("\n--- Python原生list操作 ---")
    py_list = [10, 20, 30, 40, 50]
    print(f"原始列表: {py_list}")
    print(f"大小: {len(py_list)}")
    print(f"内存占用: {sys.getsizeof(py_list)} 字节")
    
    # 应用场景演示
    example_lookup_table()
    example_numpy_array()
    example_cache()
    example_python_list_features()
    
    # 优势与局限
    print("\n╔════════════════════════════════════════╗")
    print("║   优势与局限                           ║")
    print("╚════════════════════════════════════════╝")
    print("\n✅ 优势:")
    print("  1. O(1)随机访问速度")
    print("  2. 动态大小，自动扩容")
    print("  3. 丰富的内置方法")
    print("  4. 支持负索引、切片等高级特性")
    print("  5. 可以存储不同类型元素")
    
    print("\n⚠️ 局限:")
    print("  1. 插入/删除需要移动元素，O(n)复杂度")
    print("  2. 存储对象引用，额外开销")
    print("  3. 相比C数组，速度较慢")
    print("  4. 扩容时需要复制所有数据")
    
    print("\n💡 最佳使用场景:")
    print("  - 需要频繁随机访问")
    print("  - 使用Python的高级特性（切片、推导式）")
    print("  - 快速原型开发")
    print("  - 数据分析（配合NumPy）")
    
    print("\n🐍 Python特色:")
    print("  - list是最常用的数据结构")
    print("  - 配合NumPy可进行高效科学计算")
    print("  - 语法简洁，易于使用")
    print("  - 动态类型，灵活性强")


if __name__ == "__main__":
    main()
